The invention is in the field of machine-implemented digital filters in which filter section multiplication is performed using a lookup table (LUT). More particularly, this invention is concerned with lookup table multiplication in which operand bit grouping results in a reduction in the table size necessary to produce all possible products of two multi-bit operands by LUT multiplication.
Digital filtration is a well-known technique which is implemented by a multi-stage apparatus in which the jth stage generates a product produced by multiplying the instantaneous value of a filter input X(t) and a filter stage coefficient Kj. For example, a digital finite impulse response (FIR) filter is given by: ##EQU1## Equation (1) represents an FIR filter with constant coefficients. The apparatus which implements the filter of equation (1) consists of N stages. At each stage, the jth coefficient K.sub.j is multiplied by X(t-j) to produce a product. Y(t) is obtained by taking the sum of all of the products. The FIR filter of equation 1 is represented in transposed canonical form by the apparatus of FIG. 1. In FIG. 1, each coefficient K.sub.j is 1 bits wide; X(t) is m bits wide; the product Y.sub.j (t) of XxK.sub.j is n bits wide, where n=m+1. The final result Y(t) is the sum of the N XxK products.
If the circuit of FIG. 1 is a hard-wired filter, the multiplication function for each stage denoted by reference numeral 10 can be a high-speed binary multiplier which generates and combines a plurality of partial products for each value of X to produce Y.sub.j. Such a multiplier accepts the two multi-bit operands X(t) and K.sub.j in either signed or unsigned form. One such multiplier is taught, for example, in pending U.S. Patent application Ser. No. 291,659, filed on Dec. 28, 1988, U.S. Pat. No. 4,926,371, and assigned to the assignee of this application.
Another form of hard-wired, high-speed multiplication utilizes a lookup table (LUT) in which all possible products of X(t) and K.sub.j are stored. Each product is stored at an address location corresponding to the magnitude of X which, when multiplied by K.sub.j, results in the product stored at the addressed location. In LUT multiplication, the operation consists essentially of providing the instantaneous value of X at the address port of the memory in which the LUT is stored, which "reads out" the product stored at the addressed location.
The technique of LUT multiplication is very fast and its speed increases with the provision of memories which operate at video speeds. The required basic hardware component for a LUT multiplier comprises a memory and associated address circuitry. However, a substantial amount of memory is required to store all possible products of X(t) and K.sub.j. In an N stage filter, the memory requirement is compounded because a LUT is required for each stage.
The simplicity and high speed of LUT multiplication makes it extremely attractive for multiple-stage sum-of-product mechanisms such as digital filters. Therefore, there is an evident need to provide a LUT multiplier which affords the desired speed, but which reduces the total amount of memory required to implement the technique.